package demo1;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-26
 * Time: 20:05
 */
public class TestDemo {
    public static class Machine{
        public int workPoint;//咖啡机可用时间点
        public int workTime;//咖啡机的工作时间

        public Machine(int workPoint,int workTime){
            this.workPoint = workPoint;
            this.workTime = workTime;
        }
    }

    public static class MachineComparator implements Comparator<Machine> {
        @Override
        public int compare(Machine o1, Machine o2) {
            return (o1.workTime + o1.workPoint) - (o2.workTime + o2.workPoint);
        }
    }

    //给你一个数组arr代表咖啡机冲一杯咖啡的时间,和N个人,
    // 请返回N个人最短时间冲完咖啡的时间=>代表每个人的时间

    //arr->表示代表咖啡机冲一杯咖啡的时间
    //N ->N个人
    //a -> 洗一个咖啡杯所需要的时间
    //b -> 一个咖啡杯挥发干净的时间
    public static int minTime(int[] arr,int N,int a,int b){
        PriorityQueue<Machine> heap = new PriorityQueue<>(new MachineComparator());
        //将每一个咖啡机的开始工作点都设置为1
        for(int i =0;i<arr.length;++i){
            heap.add(new Machine(0,arr[i]));
        }
        //生成一个drink数组表示==>一个人喝完咖啡所用的时间
        int[] drink = new int[N];
        //然后对于每一个人
        for(int i =0;i<N;++i){
            //弹出最优时间点
            Machine cur = heap.poll();
            //当前时间带你累加所消耗的时间并记录
            cur.workPoint += cur.workTime;
            //将完成喝咖啡的时间放到drink数组里面
            drink[i] = cur.workPoint;
            heap.add(cur);//重新放回堆中
        }
        //free代表什么时候洗的机器可用
      //  return bestTime(drink,a,b,0,0);
        return bestTimeDP(drink,a,b);
    }

    //可变参数为index ,free
    public static int bestTime(int[] drinks,int wash,int air,int index,int free){
        if(index == drinks.length){
            //如果没有杯子了,那么最好时间为0
            return 0;
        }
        //接下来洗杯子有两种选择
        //1.选择去洗
        //洗index位置的咖啡杯所需要消耗的时间
        //必须是咖啡喝完并且是洗的机器是可用的===>所以取得两个最大值 然后在加上洗的时间wash
        int selfClean1 = Math.max(drinks[index],free) + wash;
        //剩余人洗咖啡杯的时间
        //剩余人的洗咖啡机时必须等待index位置的人洗完才能洗
        //所以咖啡机可用时间就为index位置洗干净的时间
        int restClean1 = bestTime(drinks,wash,air,index+1,selfClean1);
        int p1 = Math.max(selfClean1,restClean1);
        //2.选择去挥发
        int selfClean2 = drinks[index] + air;
        int restClean2 = bestTime(drinks,wash,air,index+1,free);
        int p2 = Math.max(selfClean2,restClean2);
        return Math.min(p1,p2);
    }


//======================================改动态规划=============================================

    public static int bestTimeDP(int[] drinks,int wash,int air){
        int N = drinks.length;
        //可变参数为index,free
        //由于这里的free的区间范围不确定===>要顾及free的最大范围
        int maxFree = 0;
        for(int i =0;i< drinks.length;++i){
            //也就是所有人都洗
            maxFree += Math.max(drinks[i],maxFree) + wash;
        }
        int[][] dp = new int[N+1][maxFree +1];
        //从下往上填
        for(int index = N-1;index>=0;index--){
            for(int free = 0;free<=maxFree;++free){
                int selfClean1 = Math.max(drinks[index],free) + wash;
                if(selfClean1>maxFree){
                    continue;
                }
                //剩余人洗咖啡杯的时间
                //剩余人的洗咖啡机时必须等待index位置的人洗完才能洗
                //所以咖啡机可用时间就为index位置洗干净的时间
                int restClean1 = dp[index+1][selfClean1];
                int p1 = Math.max(selfClean1,restClean1);
                //2.选择去挥发
                int selfClean2 = drinks[index] + air;
                int restClean2 = dp[index+1][free];
                int p2 = Math.max(selfClean2,restClean2);
                dp[index][free] = Math.min(p1,p2);
            }
        }
        return dp[0][0];
    }


//=========================================TEST===========================================
    // 验证的方法
    // 彻底的暴力
    // 很慢但是绝对正确
    public static int right(int[] arr, int n, int a, int b) {
        int[] times = new int[arr.length];
        int[] drink = new int[n];
        return forceMake(arr, times, 0, drink, n, a, b);
    }

    // 每个人暴力尝试用每一个咖啡机给自己做咖啡
    public static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
        if (kth == n) {
            int[] drinkSorted = Arrays.copyOf(drink, kth);
            Arrays.sort(drinkSorted);
            return forceWash(drinkSorted, a, b, 0, 0, 0);
        }
        int time = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int work = arr[i];
            int pre = times[i];
            drink[kth] = pre + work;
            times[i] = pre + work;
            time = Math.min(time, forceMake(arr, times, kth + 1, drink, n, a, b));
            drink[kth] = 0;
            times[i] = pre;
        }
        return time;
    }

    public static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) {
        if (index == drinks.length) {
            return time;
        }
        // 选择一：当前index号咖啡杯，选择用洗咖啡机刷干净
        int wash = Math.max(drinks[index], washLine) + a;
        int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));

        // 选择二：当前index号咖啡杯，选择自然挥发
        int dry = drinks[index] + b;
        int ans2 = forceWash(drinks, a, b, index + 1, washLine, Math.max(dry, time));
        return Math.min(ans1, ans2);
    }


    // for test
    public static int[] randomArray(int len, int max) {
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * max) + 1;
        }
        return arr;
    }

    // for test
    public static void printArray(int[] arr) {
        System.out.print("arr : ");
        for (int j = 0; j < arr.length; j++) {
            System.out.print(arr[j] + ", ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int len = 10;
        int max = 10;
        int testTime = 10;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = randomArray(len, max);
            int n = (int) (Math.random() * 7) + 1;
            int a = (int) (Math.random() * 7) + 1;
            int b = (int) (Math.random() * 10) + 1;
            int ans1 = right(arr, n, a, b);
            int ans2 = minTime(arr, n, a, b);
         //   int ans3 = minTime2(arr, n, a, b);
            if (ans1 != ans2) {
                printArray(arr);
                System.out.println("n : " + n);
                System.out.println("a : " + a);
                System.out.println("b : " + b);
                System.out.println(ans1 + " , " + ans2);
                System.out.println("出现错误");
                System.out.println("===============");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
